package week02;

import java.math.BigInteger;

import javax.swing.plaf.multi.MultiInternalFrameUI;

public class T015 {
	
	//method: 组合数
	//递归公式求：C(n,m)=C(n-1,m-1)+C(n-1,m)
	//规定C(n,0)=C(n,n)=1
	//特别的，当x<y时，C(x,y)不存在
//	public static void run(int m,int n) {
//		int all=m+n;
//		long [][] combination = new long[all+1][all+1];
//		for(int i=0;i<=all;++i) {
//			combination[i][0]=combination[i][i]=1;
//			for(int j=1;j<=i;++j) {
//				combination[i][j]=combination[i-1][j-1]+combination[i-1][j];
//			}
//		}
//		System.out.println(combination[m+n][m]);
//	}
	
	//阶乘求组合数
	//n中选m个：C(n,m)=n!/m!/(n-m)!
//	public static void run(int m,int n) {
//		BigInteger num = new BigInteger("1");
//		for(int i=2;i<=m+n;i++) num=num.multiply(BigInteger.valueOf(i));
//		for(int i=2;i<=m;i++) num=num.divide(BigInteger.valueOf(i));
//		for(int i=2;i<=n;i++) num=num.divide(BigInteger.valueOf(i));
//		System.out.println(num);
//	}
	
	
	//method2:  dp
    //因为 只能向右或向下移动
    //所以 到达(i,j)这个点的路径条数由(i-1,j)和(i,j-1)得出
    //dp[i][j]=dp[i-1][j]+dp[i][j-1],其中,当i或j等于0时dp[i][j]=1;
//	public static void run(int m,int n) {
//		long[][] dp = new long[m+1][n+1];
//		for(int i=0;i<=m;i++) dp[i][0]=1;
//		for(int i=0;i<=n;i++) dp[0][i]=1;
//		for(int i=1;i<=m;i++) {
//			for(int j=1;j<=n;j++) {
//				dp[i][j]=dp[i-1][j]+dp[i][j-1];
//			}
//		}
//		System.out.println(dp[m][n]);
//	}
	
	//method2:  滚动数组优化dp空间复杂度
    //对于method2的dp条件，我们发现每次的结果只跟dp[i-1][j]与dp[i][j-s1]有关
    //而其他的空间是用不到的，即仅与前一行有关
    //所以我们可以将第一维度的m降至2
//	public static void run(int m,int n) {
//		long dp[][] = new long[2][n+1];
//		for(int i=0;i<=n;i++) dp[0][i]=1;
//		dp[1][0]=1;
//		for(int i=1;i<=m;i++) {
//			for(int j=1;j<=n;j++) {
//				dp[i&1][j]=dp[(i-1)&1][j]+dp[i&1][j-1];
//			}
//		}
//		System.out.println(dp[m&1][n]);
//	}
	
	public static void run(int r,int c) {
		long[][] dp = new long[2][c+1];
		for(int i=0;i<=c;i++) {
			dp[0][i]=1;
		}
		dp[1][0]=1;
		for(int i=1;i<=r;i++) {
			for(int j=1;j<=c;j++) {
				dp[i&1][j]=dp[(i-1)&1][j]+dp[i&1][j-1];
			}
		}
		System.out.println(dp[r&1][c]);
 	}
	public static void main(String[] args) {
		run(20, 20);
	}
}
